/* Expected output::
1 : Int
2. : Real
hello world : [Char]
#t : Boolean
2 : Int
#f : Boolean
#t : Boolean
#t : Boolean
720 : Int
#f : Boolean
9. : Real
20 : Int
17 : Int
20 : Int
20 : Int
20 : Int
40 : Int
[1, 1, 2, 3, 5, 8, 13, 21, 34] : Dynamic
[3,6,4,8,9,5,3,2,1,2,0,8,6,4,3,7,3,4,9] : [Int]
[0,1,2,2,3,3,3,3,4,4,4,5,6,6,7,8,8,9,9] : [Int]
120 : Dynamic
120 : Dynamic
[2,3,5] : [Int]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] : [Int]
[0,1,2] : [Int]
*/


// Library import

using "lists.nr";

// Basic values

1; 2.0; "hello world"; #t; x:Int -> Int => x + x; x:Int * y:Int -> Int => x + y;

// Basic operations

1 + 1;
#t && #f;
#t || #f;
8 > 2;
6!;
!#t;
3.0 ^ 2.0;
(x:Int -> Int => x + x) 10;


// Let testing

x:Int := 7,
x + 10;

double:[x:Int -> Int] := x + x,
double 10;

double:[x:Int -> Int] := x + x,
y:Int := 10,
double y;

//Testing scope of variables
double:[x:Int -> Int] := x + x,
x:Int := 10,
double x;

double:[x:Int -> Int] := x + x,
quadruple:[x:Int -> Int] := double (double x),
x:Int := 10,
quadruple x;

// Recursion testing

fibonacci:[x:Int -> Int] <- 
	if 	x <= 0 
	then	0
	else if x = 1
	then 	1
	else 	(fibonacci (x - 1)) + (fibonacci (x - 2))
	/if;

// Multiple argument testing

map:[fun:[Dynamic -> Dynamic] * lst:[Dynamic] -> [Dynamic]] <-
	match lst with
		head::tail 	=> (fun head) :: (map fun tail)
	|	else		=> nil
	/match;

inums:[x:Int * y:Int -> [Int]] <-
	if	x >= y
	then 	nil
	else 	x :: (inums (x + 1) y)
	/if;

map fibonacci (inums 1 10);

// Dynamic Testing 

dyn_dub:[x:Dynamic -> Int] <- x + x;

vbad_exp:[x:Int -> Dynamic] <-
	x + 2.0;

bad_exp:[x:Int -> Dynamic] <- 
	if 	x > 2 
	then	#t
	else 	x
	/if;

unbad_exp:[x:Int -> Dynamic] <- 
	if*	x > 2 
	then	#t
	else 	x
	/if;

rtbad_exp:[x:Int -> Int] <- 
	if* 	x > 2 
	then	#t
	else 	x
	/if;

// Mutual recursion

abs:[x:Int -> Int] <-
	   if x < 0
	   then (-x)
	   else x
	   /if;

even:[x:Int -> Boolean] <-
	    if 	x = 0
	    then #t
	    else (odd ((abs x) - 1))
	    /if
& odd:[x:Int -> Boolean] <-
	   if x = 0
	   then #f
	   else (even ((abs x) - 1))
	   /if;
	   
// Larger algorithms 

mergesort:[lst:[Dynamic] -> [Dynamic]] <-
	// Split subroutine
	split:[lst:[Dynamic] -> [[Dynamic] * [Dynamic]]] := 
		len:Int := length lst,
		if 	len = 0
		then 	cons nil nil
		else if len = 1 
		then	cons lst nil
		else 	cons (sublist lst 1 (len / 2)) (sublist lst (len / 2 + 1) len)
		/if,
	// Merge subroutine
	mergelists:[l1:[Dynamic] * l2:[Dynamic] -> [Dynamic]] := 
		match l1 with
			h1::t1 	=> (match l2 with
					h2::t2	=> (
						if 	h1 < h2 
						then	h1 :: (mergelists t1 l2)
						else 	h2 :: (mergelists l1 t2)
						/if
						)
				|	else	=> l1
				/match
			)
		|	else 	=> l2
		/match,
	// Split, recurse, and merge
	if 	(length lst) < 2 
	then 	lst
	else 	lists:[[Dynamic] * [Dynamic]] := split lst,
		mergelists (mergesort (car lists)) 
			   (mergesort (cdr lists))
	/if;

unsorted:[Int] <- [3,6,4,8,9,5,3,2,1,2,0,8,6,4,3,7,3,4,9];
unsorted;
sorted:[Int] <- mergesort unsorted;
sorted;

// Z combinator

z <- f => (x => f (y => (x x) y)) (x => f (y => (x x) y));

z_fact:[f -> [Int -> Int]] <- 
       	  (x:Int -> Int => 
	  	 if x = 0 
		 then 1 
		 else x * (f (x - 1)) 
		 /if
	  );

my_fact <- (z z_fact);

(z z_fact) 5;
my_fact 5;

// String conversion

string_of_int:[x:Int -> String] <- 
	string_of_digit:[x:Int -> String] :=
		if	x = 0
		then 	"0"
		else if	x = 1
		then 	"1"
		else if	x = 2
		then 	"2"
		else if	x = 3
		then 	"3"
		else if	x = 4
		then 	"4"
		else if	x = 5
		then 	"5"
		else if	x = 6
		then 	"6"
		else if	x = 7
		then 	"7"
		else if	x = 8
		then 	"8"
		else 	"9"
		/if,
	if 	x < 10
	then 	string_of_digit x
	else 	concat (string_of_int (x / 10)) (string_of_digit (x % 10))
	/if;


string_of_intlist:[l:[Int] -> String] <- 
	match l with
		head::tail	=> concat (concat (string_of_int head) " ") (string_of_intlist tail)
	|	else		=> ""
	/match;

// Sieve of Eratosthenes

primes:[max:Int -> [Int]] <- 
	euler:[primes:[Int] -> [Int]] :=
		match primes with
			head::tail	=> head :: (euler (listsub tail
				 (map (x:Int -> Int => x * head) primes)))
		|	else		=> []
		/match,
	euler (inums 2 (max + 1));

primes 5;
primes 100;

// Church Numerals

church_to_decimal:[cn:[[Int -> Int] -> [Int -> Int]] -> Int] <-
	nsucc:[n:Int -> Int] := n + 1,
	(cn nsucc) 0;

c0 <- s => z => z;
csucc <- n => f => z => f ((n f) z);
c1 <- csucc c0;
c2 <- csucc c1;

[church_to_decimal c0, church_to_decimal c1, church_to_decimal c2];
